import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合
// 答案 不能 包含重复的组合。返回的答案中，组合可以按 任意顺序 排列
// 注意其实要求返回的不是子集，因为子集一定是不包含相同元素的，要返回的其实是不重复的组合
// 比如输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
// 测试链接 : https://leetcode.cn/problems/subsets-ii/
public class subsetsWithDup {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();

        func(nums,0,new int[nums.length],0,ans);

        return ans;
    }

    public void func(int[] nums, int pos, int[] path, int size, List<List<Integer>> ans ){
        if(pos == nums.length){
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                list.add(path[i]);
            }
            ans.add(list);
        }else{
            int next = pos+1;

            while (next < nums.length && nums[next] == nums[pos]){
                next++;
            }
            func(nums,next,path,size,ans);

            for( ; pos < next; pos++){
                path[size++] = nums[pos];
                func(nums,next,path,size,ans);
            }
        }
    }
}
